package main.leetcode.clockin.September;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 *
 * <p>给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * <p>示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
 */
public class day8 {
    private List<List<Integer>> res;

    public static void main(String[] args) {
        System.out.println(new day8().combine(4, 2));
    }

    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        if (k == 0) {
            return res;
        }
        backTrack(1, new ArrayList<>(), n, k);
        return res;
    }

    private void backTrack(int num, List<Integer> cur, int n, int k) {
        if (cur.size() == k) {
            res.add(new ArrayList<>(cur));
            return;
        }
        // 如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了。
        // 这是因为：即使把 5 选上，后面的数只有 6 和 7，一共就 3 个候选数，凑不出 4个数的组合。因此，搜索起点有上界。
        for (int i = num; i <= n - (k - cur.size()) + 1; ++i) {
            cur.add(i);
            backTrack(i + 1, cur, n, k);
            cur.remove(cur.size() - 1);
        }
    }
}
